package top100

import "sort"

/**
 * @description: 322.零钱兑换
 * @keyword:
 * @author: kami
 * @date 2024/1/6 22:34
 */
func coinChange(coins []int, amount int) int {
	var maxA = amount + 1
	dp := make([]int, maxA)
	for i := 0; i < maxA; i++ {
		dp[i] = maxA
	}
	dp[0] = 0
	for i := 0; i < len(coins); i++ {
		for j := coins[i]; j <= amount; j++ {
			var pre = dp[j-coins[i]] + 1
			if pre < dp[j] {
				dp[j] = pre
			}
		}
	}
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}

func searchInsert(nums []int, target int) int {
	if target <= nums[0] {
		return 0
	}
	if target > nums[len(nums)-1] {
		return len(nums)
	}

	var left = 0
	var right = len(nums) - 1
	for left <= right {
		var mid = (left + right) / 2
		if nums[mid] == target {
			return mid
		} else if nums[mid] > target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

func findMin(nums []int) int {
	var left = 0
	var right = len(nums) - 1
	for left <= right {
		if nums[left] <= nums[right] {
			return nums[left]
		}
		var mid = left + (right-left)/2
		if nums[mid] >= nums[left] {
			left = mid + 1
		} else {
			right = mid
		}
	}
	return -1
}

func longestConsecutive(nums []int) int {
	if len(nums) < 2 {
		return len(nums)
	}
	var numCnt = make(map[int]int, len(nums))
	for i := 0; i < len(nums); i++ {
		numCnt[nums[i]] = 1
	}
	var maxCnt = 1
	for i := 0; i < len(nums); i++ {
		if cnt, ok := numCnt[nums[i]-1]; ok {
			var curCnt = 1 + cnt
			var offset = 2
			delete(numCnt, nums[i]-1)
			for numCnt[nums[i]-offset] > 0 {
				curCnt += numCnt[nums[i]-offset]
				delete(numCnt, nums[i]-offset)
				offset++
			}
			numCnt[nums[i]] = curCnt
			if curCnt > maxCnt {
				maxCnt = curCnt
			}
		}
	}
	return maxCnt
}

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	var m = len(nums1)
	var n = len(nums2)
	if m > n {
		return findMedianSortedArrays(nums2, nums1)
	}
	var iMin = 0
	var iMax = m
	for iMin <= iMax {
		var i = (iMin + iMax) / 2
		var j = (m+n+1)/2 - i // 推导的 i+j的是长度的一半
		if j != 0 && i != m && nums2[j-1] > nums1[i] {
			iMin = i + 1
		} else if i != 0 && j != n && nums1[i-1] > nums2[j] {
			iMax = i - 1
		} else {
			var maxLeft = 0
			if i == 0 {
				maxLeft = nums2[j-1]
			} else if j == 0 {
				maxLeft = nums1[i-1]
			} else {
				maxLeft = getMax(nums1[i-1], nums2[j-1])
			}
			if (m+n)%2 == 1 {
				return float64(maxLeft)
			}
			var minRight = 0
			if i == m {
				minRight = nums2[j]
			} else if j == n {
				minRight = nums1[i]
			} else {
				minRight = getMin(nums1[i], nums2[j])
			}
			return float64((maxLeft + minRight)) / 2.0
		}

	}
	return 0
}
func getMax(num1, num2 int) int {
	if num1 > num2 {
		return num1
	}
	return num2
}
func getMin(num1, num2 int) int {
	if num1 > num2 {
		return num2
	}
	return num1
}
func isValid(s string) bool {
	var queue []byte
	for i := 0; i < len(s); i++ {
		if len(queue) == 0 {
			queue = append(queue, s[i])
		} else {
			if invalid(queue[len(queue)-1], s[i]) {
				return false
			}
			if isPair(queue[len(queue)-1], s[i]) {
				queue = queue[:len(queue)-1]
			} else {
				queue = append(queue, s[i])
			}
		}
	}
	return len(queue) == 0
}

func isPair(s1, s2 byte) bool {
	if s1 == '(' && s2 == ')' {
		return true
	}
	if s1 == '[' && s2 == ']' {
		return true
	}
	if s1 == '{' && s2 == '}' {
		return true
	}
	return false
}
func invalid(s1, s2 byte) bool {
	if s1 == '(' && (s2 == ']' || s2 == '}') {
		return true
	}
	if s1 == '[' && (s2 == '}' || s2 == ')') {
		return true
	}
	if s1 == '{' && (s2 == ']' || s2 == ')') {
		return true
	}
	return false
}

func dailyTemperatures(temperatures []int) []int {
	var res = make([]int, len(temperatures))
	res[len(res)-1] = 0
	var stack []int
	for i := 0; i < len(temperatures); i++ {
		for len(stack) > 0 {
			if temperatures[i] > temperatures[stack[len(stack)-1]] {
				res[stack[len(stack)-1]] = i - stack[len(stack)-1]
				stack = stack[:len(stack)-1]
				continue
			}
			break
		}
		stack = append(stack, i)

	}
	return res
}
func topKFrequent(nums []int, k int) []int {
	var cntMap = make(map[int]int)
	for i := 0; i < len(nums); i++ {
		cntMap[nums[i]]++
	}
	var frequentMap = make(map[int][]int)
	var cntNums []int
	for k, v := range cntMap {
		if val, ok := frequentMap[v]; ok {
			frequentMap[v] = append(val, k)
		} else {
			cntNums = append(cntNums, v)
			frequentMap[v] = append(frequentMap[v], k)
		}
	}
	sort.Ints(cntNums)
	var res []int
	for i := len(cntNums) - 1; i >= 0; i-- {
		if len(res) >= k {
			return res
		}
		res = append(res, frequentMap[cntNums[i]]...)
	}
	return res

}
